#ifndef _SEQLIST_H
#define _SEQLIST_H 

#include "Utili.h"

template <typename Type>
class SeqList
{
public:
	SeqList(size_t sz = SEQLIST_DEFAULT_SIZE)
	{
		capacity = sz > SEQLIST_DEFAULT_SIZE ? sz : SEQLIST_DEFAULT_SIZE;
		base = new Type[capacity + 1];
		len = 0;
	}
	~SeqList()
	{
		delete []base;
		base = NULL;
		capacity = len = 0;
	}
public:
	bool push_back(const Type &x)
	{
		if (IsFull() && !Inc())
		{
			return false;
		}
		base[1 + len++] = x;
		return true;
	}
	bool push_front(const Type &x)
	{
		if (IsFull() && !Inc())
		{
			return false;
		}
		for (int i = len; i > 0; --i)
			base[i + 1] = base[i];
		base[1] = x;
		len++;
		return true;
	}
	bool pop_back()
	{
		if (IsEmpty())
			return false;
		len--;
		return true;
	}
	bool pop_front()
	{
		if (IsEmpty())
			return false;
		for (int i = 1; i < len; ++i)
			base[i] = base[i + 1];
		len--;
		return true;
	}
	Type get_back()const
	{
		assert(len > 0);
		return base[len];
	}
	Type get_front()const
	{
		assert(len > 0);
		return base[1];
	}
	size_t size()const
	{
		return len;
	}
	void sort();
	void clear()
	{
		len = 0;
	}
	void showlist()const
	{
		for (int i = 1; i <= len; i++)
		{
			cout << base[i] << " ";
		}
		cout << endl;
	}
public:
	Type operator[](int pos)const
	{return base[pos];}
	Type& operator[](int pos)
	{return base[pos];}
protected:
	bool IsFull()
	{return len==capacity;}
	bool IsEmpty()
	{return len==0;}
protected:
	bool Inc()
	{
		Type *base_new = new Type[capacity + len + 1];
		if (base_new == NULL)
			return false;
		memcpy(base_new, base, (capacity+1)*sizeof(Type));
		capacity += INC_SIZE;
		delete[]base;
		base = base_new;
		return true;
	}
private:
	enum { SEQLIST_DEFAULT_SIZE = 20, INC_SIZE = 10 };
	Type *base;
	size_t capacity;
	size_t len;
};

#endif
